const int mx = 31622;
int pi[mx + 1];
auto init = [] {
    for (int i = 2; i <= mx; i++) {
        if (pi[i] == 0) {
            // i是质数，标记他
            pi[i] = pi[i - 1] + 1;

            // 埃氏筛
            for (int j = i * i; j <= mx; j += i)
                pi[j] = -1;     // 标记 i 的倍数为合数
        } else
            pi[i] = pi[i - 1];
    }
    return 0;
}();

class Solution {
    /*
    由规律可得，特殊数字是 质数的平方
    所以我们要找的就是[l, r]中哪些数是质数的平方，然后减掉这些数
    我们先来想想[1, r]中平方数的个数是多少? ---> floor(sqrt(r))
    接下来想想[1, floor(sqrt(i))]中有多少个质数，记作pi(i);
    利用前缀和的思想
    pi(i) = pi(i - 1) + bool(i是质数)
*/
    // 埃氏筛，由于 1 <= l <= r <= 10^9 ，那么sqrt(10^9) ≈ 31622
    // 也就是说[l, r]区间中有31622个平方数，现在我们来排查哪些数是质数，因为我们要找的是质数的平方

public:
    int nonSpecialCount(int l, int r) {
        // 统计[l, r]中哪些是质数的平方
        // 1. 求出[1, r]中哪些数是普通数的平方，求出多少个平方数，也就是sqrt(r)
        // 2. 在这些普通数找质数，再找[0, sqrt(r)]中有多少个质数记为pi[r]
        // [l, r] = [0, r] - [0, l - 1]
        // 由于pi[i]记录的是[0, sqrt(i)]中质数的个数
        // 所以[l, r] = [0, r] - [0, l - 1] = pi[(int)sqrt(r)] - pi[(int)sqrt(l - 1)]
        return r - l + 1 - (pi[(int)sqrt(r)] - pi[(int)sqrt(l - 1)]);
    }
};